﻿//#include <iostream>
//#include <cstring>
//#include <string>
//using namespace std;
//int main()
//{
//	string s;
//	char str[6000];
//	fgets(str, 6000, stdin);
//	if (str[0] >= 'A' && str[0] <= 'Z')
//	{
//		s.push_back(str[0]);
//	}
//	else
//	{
//		s.push_back(str[0] - 32);
//	}
//	for (int i = 1; i < strlen(str); i++)
//	{
//		if (str[i - 1] == ' ' && str[i] != ' ')
//		{
//			if (str[i] >= 'A' && str[i] <= 'Z')
//			{
//				s.push_back(str[i]);
//			}
//			else
//			{
//				s.push_back(str[i] - 32);
//			}
//		}
//	}
//	cout << s << endl;
//	return 0;
//}

//#include <iostream>
//using namespace std;
//int main()
//{
//    int n = 0;
//    int x = 0, y = 1, z = 0, count = 0;
//    cin >> n;
//    while (1)
//    {
//        z = x + y;
//        if (z == n)
//        {
//            break;
//        }
//        else if (z > n)
//        {
//            if (n - y < z - n)
//            {
//                count = n - y;
//            }
//            else
//            {
//                count = z - n;
//            }
//            break;
//        }
//        else
//        {
//            x = y;
//            y = z;
//        }
//    }
//    cout << count << endl;
//    return 0;
//}

//#include <iostream>
//#include <vector>
//using namespace std;
//int main()
//{
//    int n = 0;
//    cin >> n;
//    vector<vector<int>> v(n + 1);
//    for (int i = 1; i <= n; i++)
//    {
//        v[i].resize(i + 1, 0);
//        for (int j = 1; j <= i; j++)
//        {
//            if (j == 1 || j == i)
//            {
//                v[i][j] = 1;
//            }
//            else
//            {
//                v[i][j] = v[i - 1][j - 1] + v[i - 1][j];
//            }
//            fprintf(stdout, "%5d", v[i][j]);
//        }
//        cout << endl;
//    }
//    return 0;
//}

//class Solution {
//public:
//    bool Find(int x, int y, vector<string>& vs, string& str, int n, int a = 1, int b = 1, int c = 1, int d = 1)
//    {
//        if (n == str.size())
//        {
//            return true;
//        }
//        //上
//        int w = y - 1;
//        if (a && w >= 0 && vs[w][x] == str[n])
//        {
//            n++;
//            a = 1;
//            b = 0;
//            c = 1;
//            d = 1;
//            return Find(x, w, vs, str, n, a, b, c, d);
//        }
//        //下
//        int s = y + 1;
//        if (b && s < vs.size() && vs[s][x] == str[n])
//        {
//            n++;
//            a = 0;
//            b = 1;
//            c = 1;
//            d = 1;
//            return Find(x, s, vs, str, n, a, b, c, d);
//        }
//        //左
//        int A = x - 1;
//        if (c && A >= 0 && vs[y][A] == str[n])
//        {
//            n++;
//            a = 1;
//            b = 1;
//            c = 1;
//            d = 0;
//            return Find(A, y, vs, str, n, a, b, c, d);
//        }
//        //右
//        int D = x + 1;
//        if (d && D < vs[x].size() && vs[y][D] == str[n])
//        {
//            n++;
//            a = 1;
//            b = 1;
//            c = 0;
//            d = 1;
//            return Find(D, y, vs, str, n, a, b, c, d);
//        }
//        return false;
//    }
//    bool exist(vector<string>& board, string word)
//    {
//        for (int i = 0; i < board.size(); i++)
//        {
//            for (int j = 0; j < board[i].size(); j++)
//            {
//                if (word[0] == board[i][j])
//                {
//                    int k = 1;
//                    bool p = Find(j, i, board, word, k);
//                    if (p == true)
//                    {
//                        return p;
//                    }
//                }
//            }
//        }
//        return false;
//    }
//};